package com.sy.algorithm;

import java.util.HashMap;

/**
 *
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 *
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 * 示例 2：
 *
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 * 示例 3：
 *
 * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 * 输出：[8,9,9,9,0,0,0,1]
 *
 *
 * 提示：
 *
 * 每个链表中的节点数在范围 [1, 100] 内
 * 0 <= Node.val <= 9
 * 题目数据保证列表表示的数字不含前导零
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author zb
 * @Date 2022/3/8 19:02
 */
public class Algorithm002 {
    public static void main(String[] args){

        Solution solution = new Solution();

        ListNode l1 = createListNode(new int[]{9,9,9,9,9,9,9});
        ListNode l2 = createListNode(new int[]{9,9,9,9});

        ListNode listNode = solution.addTwoNumbers(l1,l2);
        printListNode(listNode);
    }

    private static class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode parent = new ListNode((l1.val+l2.val)%10);
            ListNode resultChild;
            ListNode result = parent;

            int add = (l1.val+l2.val)/10;
            while(l1.next != null || l2.next != null){
                if(l1.next != null && l2.next != null){
                    int add2 = l1.next.val + l2.next.val + add;
                    add = add2/10;
                    resultChild = new ListNode(add2%10);
                    parent.next = resultChild;
                    parent = resultChild;

                    l1 = l1.next;
                    l2 = l2.next;
                }else if(l1.next != null){
                    int add2 = l1.next.val + add;
                    add = add2/10;
                    resultChild = new ListNode(add2%10);
                    parent.next = resultChild;
                    parent = resultChild;

                    l1 = l1.next;
                }else if(l2.next != null){
                    int add2 = l2.next.val + add;
                    add = add2/10;
                    resultChild = new ListNode(add2%10);
                    parent.next = resultChild;
                    parent = resultChild;

                    l2 = l2.next;
                }
            }
            if(add>0){
                resultChild = new ListNode(add);
                parent.next = resultChild;
            }
            return result;
        }
    }

    static public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    private static ListNode createListNode(int[] nums){
        ListNode child = new ListNode(nums[nums.length-1]);
        ListNode parent = child;
        if(nums.length>1){
            for (int i = nums.length - 2; i >= 0 ; i--) {
                parent = new ListNode(nums[i],child);
                child = parent;
            }
        }
        return parent;
    }
    private static void printListNode(ListNode listNode){
        System.out.print(listNode.val);
        while(listNode.next != null){
            System.out.print(" "+listNode.next.val);
            listNode = listNode.next;
        }
    }
}
